package jjn.round1;

/**
 * @author Jjn
 * @since 2022-08-24 16:33
 */
public class LeetCode74_SearchA2dMatrix {
    
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }
        int height = matrix.length;
        int width = matrix[0].length;
        // 二分查找 定位行
        int low = 0, high = height - 1;
        while (low <= high) {
            int midLine = low + (high - low) / 2;
            int[] midArray = matrix[midLine];
            int firstOfMid = midArray[0];
            int lastOfMid = midArray[width - 1];
            if (firstOfMid == target) {
                return true;
            }
            if (firstOfMid > target) {
                high = midLine - 1;
            } else if (lastOfMid >= target) {
                return containsInArray(midArray, target);
            } else {
                low = midLine + 1;
            }
        }
        return false;
    }
    
    private boolean containsInArray(int[] array, int target) {
        int left = 0, right = array.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (array[mid] == target) {
                return true;
            }
            if (array[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return false;
    }
}
